package SingleListPractice;

import java.util.List;

/**
 * 单向非循环不带头节点的链表
  */

public class MySingleList {

    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.createList();
        mySingleList.addFirst(67);
        mySingleList.addFirst(76);
        mySingleList.addLast(56);
        mySingleList.addLast(88);
        mySingleList.addIndex(2, 100);
        mySingleList.remove(160);
        mySingleList.display();
    }

    /**
     * 节点内部类
     * 单链表是由一个个节点组成的，要把这些节点抽象出来，而节点又是一个完整的一种结构，就可以以内部类形式进行书写。
     */
    static class ListNode {
        public int val;
        public ListNode next;//存放下一个节点的地址

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//该节点是为了找到链表的第一个节点
    //第一个节点找到了，后面的节点也就都可以找到了通过next中存的地址。
    // head不初始化默认为null。

    /**
     * 打印链表里面的数据，默认从头开始打印
     */
    public void display() {
        ListNode cur = this.head;//让head始终指向第一个数据节点,如果没有这句话直接用head来进行遍历
        //那么head最后会变为null，就相当于只能遍历一次，下次遍历的时候就找不到第一个数据节点了
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    /**
     * 从任意位置开始打印
     * @param newHead
     */
    public void display(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    // 下面为错误打印
    public void display1() {
        while (this.head != null) {
            System.out.print(this.head.val + " ");
            this.head = this.head.next;
        }
    }

    /**
     * 得到单链表的长度
     */
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void createList() {
        //穷举写法
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;//让head指向链表中第一个数据元素
    }

    /**
     * 头插法
     *
     * @param data
     */
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
    }

    /**
     * 尾插法(要判断链表是否为空)
     */
    public void addLast(int data) {
        ListNode node = new ListNode(data);//想要向链表中加入的新节点
        ListNode cur = this.head;
        if (cur == null) {
            this.head = node;
        } else {
//cur!=null的话，走完while循环代表cur走完了整个链表，下面进行cur.next = node 的时候就会有null.next，就会报空指针异常
            while (cur.next != null) {
                cur = cur.next;
            }
            //走完while循环到这的时候,cur已经是尾巴节点了
            cur.next = node;
        }
    }

    /**
     * 任意位置插入,第一个数据节点为0号下标
     * 要进行index合法性的判断
     */
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            //throw相当于return
            throw new IndexWrongException("下标  范围不合法");
        }
        //链表为空的时候插入,相当于头插法
        if (index == 0) {
            addFirst(data);
            return;
        }
        //链表有元素时候，想要在最后面插入，相当于尾插法
        if (size() == index) {
            addLast(data);
            return;
        }
        //1、先走index-1步，找到cur
        ListNode cur = findIndexSubOne(index);//找到要插入的位置前面的那一个节点
        ListNode node = new ListNode(data);//要插入的节点
        //2、修改指向
        ListNode del = cur.next;//记录原来链表中位于index位置的节点
        node.next = del;
        cur.next = node;
    }

    private ListNode findIndexSubOne(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    /**
     * 删除第一次出现关键字为key的节点
     */
    public void remove(int key) {
        //1、先判断链表是否为空
        if (this.head == null) {
            return;
        }
        //2、考虑要删除的的是头节点
        if (this.head.val == key) {
            this.head = this.head.next;//将第一个数据节点和后面的节点断掉联系
            //原来的第一个节点没人引用后就会被JVM自动回收掉。
        }
        //3、删除非第一个数据节点
        ListNode cur = findPrevOfKey(key);
        if (cur == null) {
            System.out.println("没有在链表中找到你想要删除的数字");
            return;
        }
        ListNode del = cur.next.next;
        cur.next = del;
    }

    //cur.next!=null:代表走到链表的尾巴节点 .     cur !=null代表走完了该链表
    //findPrevOfKey:找到key值前面的那个节点
    private ListNode findPrevOfKey(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null; //链表中没找到的情况
    }

    /**
     * 删除所有值为key的节点
     *
     * @param key
     */
    public void removeAllKey(int key) {
        if (this.head == null) {
            return;
        }
        ListNode prev = this.head;//prev代表要删除的节点的前驱
        ListNode cur = this.head.next;//前面的if判断就是为了避免这里出现空指针异常
        while (cur != null) { //直到cur把所有节点都遍历完
            //上述条件若写成cur.next!=null;就会造成尾巴节点如果是要删除的节点，就会无法删除尾巴节点
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;//prev = prev.next也可以
                cur = cur.next;
            }
        }
        if (this.head.val == key) {
            this.head = this.head.next;
        }
    }

    /**
     * 链表置空
     */
    public void clear() {
        this.head = null;
    }

    /**
     * 反转链表(确定第一个节点之后，后面的节点采用头插法插入链表之中即可。)
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     */
    public ListNode reverseList() {
        if (head == null || head.next == null)//链表为空或者只有一个元素就不用翻转了。
            return head;
        // 任何链表的操作都要先考虑和后面节点的绑定关系或解除联系，然后再考虑和前面节点的绑定关系。
        ListNode cur = head.next; //从第二个数据节点开始
        head.next = null;//断开第一个数据节点和后面的联系
        while (cur != null) {
            ListNode curNext = cur.next; //该节点的设定是为了插入的时候维持和后面节点的联系不要断掉
            //进行头插法
            cur.next = head;
            head = cur;//更改头节点指向
            cur = curNext;
        }
        return head;
    }

    /**
     * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
     * <p>
     * 如果有两个中间结点，则返回第二个中间结点。
     * <p>
     * 快慢指针的数学原理：(定义一个fast指针一个slow指针)
     * 1、A速度是B速度2倍的时候，A到达终点的时候B正好在这个路程一半的位置(前提：
     * A和B同时出发且路程相同)
     * 2、跑步的时候，我让你跑5m，之后我再跑，假设两人速度相同，那么中间相差的距离也就是恒定的。
     */
    public ListNode middleNode() {
        ListNode fast = head, slow = head;//最初都指向第一个数据节点
        //while循环的条件设定考虑到节点为奇数和偶数的不同情况
        //为奇数时,当fast.next == null的时候停下来，为偶数时,当fast == null的时候停下来
        while (fast != null && fast.next != null) {
            //fast!=null && fast.next != null顺序不能颠倒
            //不能写成fast.next != null &&fast!=null ,会报空指针异常
            // A && B和A || B的执行都是先执行A再执行B(从左向右执行)
            fast = fast.next.next;//走2步
            slow = slow.next;//走1步
        }
        return slow;
    }

    /**
     * https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
     * 输入一个链表，输出该链表中倒数第k个结点。
     * 采用快慢指针进行求解
     * <p>
     * 思路:
     * 1、先让fast走k-1步或k步
     * 2、再让slow和fast一起走,当fast.next == null 或fast == null的时候，slow所指的位置就是倒数第k个节点
     * 就像跑步的时候，我让你10m，你跑完这10米，咱俩一起跑，速度相同的话，那么咱俩间距离恒为10米
     *
     * @return
     */
    public ListNode FindKthToTail(int k) {
        if (k < 0 || head == null) return null;//判断k合法不合法
        ListNode fast = head;
        ListNode slow = head;
        while (k - 1 != 0) //k-1 == 0时循环就结束了（停下来）
        {
            fast = fast.next;//向后走1步
            if (fast == null) {
                return null;
            }
            k--;
        }
        while (fast.next != null) {
            //同时向后走
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    /**
     * 合并两个有序链表
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     *
     * 思路:申请一个"头节点"(虚拟节点),其本身里面的数据毫无意义，给什么都可以.
     * 该虚拟节点标志链表的头,它后面的第一个节点(数据)就是链表的第一个有效数据
     *
     * 引用变量存的是地址，如果两个引用变量地址相同，那么改变一个引用变量内部的值，那么另一个内部的值也会改变。
     */
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode head1,
                                                      MySingleList.ListNode head2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newHead;
        while (head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                tmp.next = head1;
                head1 = head1.next;
            }else {
                tmp.next = head2;
                head2 = head2.next;
            }

            System.out.println(newHead.next);
            tmp  = tmp.next;
            System.out.println(tmp);

        }
        System.out.println("==================");
        if(head1 != null) {
            tmp.next = head1;
        }
        if(head2 != null) {
            tmp.next = head2;
        }
        return newHead.next;
    }

}
